import java.util.ArrayList;
import java.util.List;

public class ColorBorder {

    public int[][] getColor(int[][] grid, int row, int col, int color){
        int m=grid.length;
        int n=grid[0].length;
        boolean[][] temp=new boolean[m][n];
        List<int[]> res=new ArrayList<>();
        int orgcolor=grid[row][col];
        dfs(grid,row,col,temp,res,orgcolor);
        for (int i = 0; i <res.size() ; i++) {
            int[] a=res.get(i);
            grid[a[0]][a[1]]=color;
        }
        return grid;

    }

    public void dfs(int[][] grid, int x, int y, boolean[][] visited, List<int[]> borders, int originalColor){
        int m=grid.length;
        int n=grid[0].length;
        boolean isBorder=false;
        int[][] dict={{0,1},{0,-1},{1,0},{-1,0}};
        for (int i = 0; i <4 ; i++) {
            int nx=dict[i][0]+x;
            int ny=dict[i][1]+y;
            if(!(nx>=0&&nx<m&&ny>=0&&ny<n&&grid[nx][ny]==originalColor)){
                isBorder=true;
            }else if(!visited[nx][ny]) {
                visited[ny][nx]=true;
                dfs(grid,nx,ny,visited,borders,originalColor);
            }
        }
        if(isBorder){
            borders.add(new int[]{x,y});
        }
    }
}
